package com.leetcode.sorts.arrays.double_point;

import java.util.Arrays;

/**
 * @Author: WuPeng
 * @Date: 2021/5/21 10:58 上午
 *
 * 977: 有序数组的平方
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 *
 * 示例 1：
 *      输入：nums = [-4,-1,0,3,10]
 *      输出：[0,1,9,16,100]
 *      解释：平方后，数组变为 [16,1,0,9,100]
 *      排序后，数组变为 [0,1,9,16,100]
 *
 * 示例 2：
 *      输入：nums = [-7,-3,2,3,11]
 *      输出：[4,9,9,49,121]
 *
 */
public class SortArraySquare_977 {

    /**
     * 解法一：直接计算平方，再排序
     */
    public static int[] solution_01(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            nums[i] *= nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }

    /**
     * 解法二：双指针、归并
     */
    public static int[] solution_02(int[] nums){
        int len = nums.length;
        int tmp = -1;
        for (int i = 0; i < len; i++) {
            if (nums[i] < 0){
                tmp = i;
            }
            else break;
        }
        int[] arr = new int[len];
        // right为第一个不为负数的下标
        int index=0, mid=tmp, right=tmp+1;

        // [0, mid] [mid+1, len] 在这两个区间进行遍历求结果，然后归并结果
        while (mid >= 0 || right < len){
            // mid<0,说明数组中没有负数，right从0开始往后遍历，并把平方后的结果放到新的数组arr中
            if (mid < 0){
                arr[index] = nums[right] * nums[right];
                right++;
            }
            // 否则，数组中有负数，当right 达到数组的最大值时，说明，负数个数多于正数，直接将负数的平方结果放入数组arr中
            else if (right == len){
                arr[index] = nums[mid] * nums[mid];
                mid--;
            }
            // 比较正数的平方与负数的平方结果的大小，小的先放入数组arr中
            else if (nums[mid] * nums[mid] < nums[right] * nums[right]){
                arr[index] = nums[mid] * nums[mid];
                mid--;
            }
            else{
                arr[index] = nums[right] * nums[right];
                right++;
            }
            index++;
        }
        return arr;
    }

    public static void main(String[] args) {
//        int[] nums = {-4,-1,0,3,10};
        int[] nums = {-4,-1,0,3,10};
//        int[] res = solution_01(nums);
        int[] res = solution_02(nums);
        System.out.println(Arrays.toString(res));
    }

}
